#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

#define in read()
#define fi first
#define se second

const int MAXN = 1e6+10;

int T,n,a[MAXN],ans,fl;
set<pii> s;
set<pii>::iterator it;

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1) + (x<<3) + (ch^48);
	return x*sgn;
}

int main (){
	#ifndef ONLINE_JUDGE
	freopen("snakes4.in","r",stdin);
	#endif
	T = in;
	n = in;
	for(int i = 1;i <= n;i++) a[i] = in;
	while(T--){
		s.clear();
		for(int i = 1;i <= n;i++) s.insert(pii(a[i],i));
		ans = 0;fl = 0;
		while(1){
			if(s.size() == 2){
				s.erase(s.begin());
				if(fl){
					if((fl-s.size()) % 2) ans = fl+1;
					else ans = fl;
				}else ans = 1;
				break;
			}
			it = s.end();it--;
			int id = (*it).se,x = (*it).fi;
			int y =  (*s.begin()).fi;
			s.erase(s.begin());s.erase(it);
			s.insert(pii(x-y,id));
			if(id != (*s.begin()).se){
				if(fl){
					if((fl - s.size())%2) ans = fl+1;
					else ans = fl;
					break;
				}
			}else if(fl == 0) fl = s.size();
		}
		printf("%d\n",ans);
		if(T != 0){
			int kk = in;
			while(kk--){
				int x = in,y = in;
				a[x] = y;
			}
		}
	}

}
